package main.滑动窗口;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author tmh
 * @date 2024/7/10 16:28
 * @description
 */
public class T76最小覆盖子串 {

    public static void main(String[] args) {
    }

    public static String minWindow(String s, String p) {
        //定义一个List保存最后最小覆盖字串的结果
        List<Integer> result = new ArrayList<>();
        //定义一个window来保存窗口里面包含的p里面的字符的值，和 一个保存字符串p里面各个字符的map
        Map<Character, Integer> window = new HashMap<>();
        Map<Character, Integer> need = new HashMap<>();

        int len = Integer.MAX_VALUE;
        //定义一个valid，该变量表示 window中保存的元素个数和need中的该元素的个数相同的时候，该元素再区间有效
        int valid = 0;
        int start = 0;
        //把p里面的字符，放入need里面 ==>初始化p
        for (int i = 0; i < p.length(); i++) {
            Integer count = need.getOrDefault(p.charAt(i), 0);
            count += 1;
            need.put(p.charAt(i), count);
        }

        int right = 0, left = 0;
        //开始对字符串s进行一个遍历，我们的滑动窗口的区间是左闭右开的区间
        while (right < s.length()) {
            //保存当前的字符
            char c = s.charAt(right);
            //right++ ==> 更新区间里面的数据
            right++;
            //更新区间的数据
            if (need.containsKey(c)) {
                //把c放入window里面
                window.put(c, window.getOrDefault(c, 0) + 1);
                //再判断window里面的这个字符出现的次数和need里面这个字符出现的个数是否相同，相同的
                //话则就valid++，代表则个字符再窗口里面出现的次数满足p里面的要求
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            //判断左面的窗口是否要收缩
            //1.如果valid==need.size(),就是说明在s串的这个区间里面存在给定的字串t(字母个数一样，相当于同构)
            while (valid == need.size()) {
                //2.那么我们就记录这个区间的长度以及区间的起始下标
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }

                //3. 获取left这个位置的值
                char d = s.charAt(left);
                //移动left，缩小窗口
                left++;
                //4. 更新window里面的数据
                if (need.containsKey(d)) {
                    //5. 再来判断更新window之前d元素的个数和need里面d元素的个数是否相同，是的话就有效值-1
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    //把window里面这个数的值-1
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        //返回满足要求的最短区间的包含t的字符的字符串
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}
